class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        s1, s2 = len(str1), len(str2)

        # ---------- 动态规划寻找最优解 ----------
        # dp[i][j] = 两个字符串当前匹配到i和j所需要的最少添加量
        dp = [[1001] * (s2 + 1) for _ in range(s1 + 1)]
        dp[0][0] = 0

        # 记录路径
        way = [[0] * (s2 + 1) for _ in range(s1 + 1)]

        for j in range(1, s2 + 1):
            dp[0][j] = j
            way[0][j] = 1
        for i in range(1, s1 + 1):
            dp[i][0] = i
            way[i][0] = 2

        for i in range(1, s1 + 1):
            for j in range(1, s2 + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    way[i][j] = 3
                else:
                    l1 = dp[i - 1][j] + 1
                    l2 = dp[i][j - 1] + 1
                    if l1 < l2:
                        dp[i][j] = l1
                        way[i][j] = 2
                    else:
                        dp[i][j] = l2
                        way[i][j] = 1

        # for row in dp:
        #     print(row)

        # ---------- 寻找最短路径 ---------
        ans = []
        i, j = s1, s2
        while i > 0 or j > 0:
            if way[i][j] == 1:
                j -= 1
                ans.append(str2[j])
            elif way[i][j] == 2:
                i -= 1
                ans.append(str1[i])
            else:
                i -= 1
                j -= 1
                ans.append(str1[i])
            # print(i, j, ":", ans)

        return "".join(reversed(ans))


if __name__ == "__main__":
    print(Solution().shortestCommonSupersequence(str1="abac", str2="cab"))  # "cabac"

    # 测试用例8/47
    print(Solution().shortestCommonSupersequence(str1="bbbaaaba", str2="bbababbb"))  # "bbabaaababb"
